package org.yimon.tool.algo.leetcode;

/**
 * @author: ym.gao
 * @description: 相交链表
 * @date: 2024/9/11 下午3:08
 */
public class LeetCode_160_GetIntersectionNode {

    public static void main(String[] args) {
        ListNode xj = new ListNode(5, new ListNode(6, new ListNode(7)));
        System.out.println(LeetCode_160_GetIntersectionNode.getIntersectionNode(new ListNode(1, new ListNode(2, new ListNode(3, xj)))
        , new ListNode(8, new ListNode(9, xj))));
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       //特殊情况判断
        if(headA == null || headB == null || headA == headB) {
            return headA;
        }
        //最小公倍数原理，先各自遍历，遍历完成后进行交换（交换后可以在相交点处相遇）
        ListNode index1 = headA, index2 = headB;
        while (index1 != null || index2 != null) {//同时为空的情况下，说明进行了交换（达到了最小公倍数的情况）
            if(index1 == index2) {//说明找到的相交点，进行返回
                return index1;
            }
            //遍历到null，进行位置交换；否则继续遍历
            index1 = index1 == null ? headB : index1.next;
            index2 = index2 == null ? headA : index2.next;
        }

        return null;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
